package xin.luna.exercise;

import xin.luna.structs.StackLinkedTable;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/** Chapter 1 Section 3 Exercise 10: 将四则运算由中缀表达式转换为后缀表达式（逆波兰运算式） */
public class C1S3E10 {
  public static void main(String[] args) {
    StackLinkedTable<String> stack = new StackLinkedTable<>();
    StringBuilder sb = new StringBuilder();

    A:
    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      switch (item) {
        case "+":
        case "-":
          while (!stack.isEmpty() && (stack.peek().equals("*") || stack.peek().equals("/"))) {
            sb.append(stack.pop());
          }
          stack.push(item);
          break;
        case "*":
        case "/":
        case "(":
          stack.push(item);
          break;
        case ")":
          while (!stack.isEmpty()) {
            String o = stack.pop();
            if (o.equals("(")) {
              continue A;
            }

            sb.append(o);
          }

          break;
        default:
          sb.append(item);
      }
    }

    while (!stack.isEmpty()) {
      sb.append(stack.pop());
    }

    StdOut.println(sb.toString());
  }
}

// ( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )
// 1 2 + 3 4 - 5 6 - * *
